package com.leetcode;

/**
 * @author fy
 * @date 2022/3/29 9:45
 */
public class Solution343 {

    private int[] maxArr;

    /**
     * 343. 整数拆分
     *
     * @param n
     * @return
     */
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            int res = 0;
            for (int i1 = 1; i1 < i; i1++) {
                res = Math.max(Math.max(res, i1 * (i - i1)), i1 * dp[i - i1]);
            }
            dp[i] = res;
        }
        return dp[n];
    }
    
    public int integerBreak1(int n) {
        maxArr = new int[n + 1];
        return breakInt(n);
    }

    private int breakInt(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 1;
        }

        if (maxArr[n] != 0) {
            return maxArr[n];
        }

        int res = -1;
        for (int i = 1; i <= n - 1; i++) {
            res = Math.max(Math.max(res, i * (n - i)), i * breakInt(n - i));
        }
        maxArr[n] = res;
        return res;
    }
    

    public static void main(String[] args) {
        new Solution343().integerBreak(3);
    }

}
